# -*- coding: utf-8 -*-            
# @Time : 2022/12/12 21:41
# @Author  : lining
# @FileName: 归并排序.py
"""
分治思想，使用递归
把两个已经有序的数组合并，变成一个新的有序的数组
时间复杂度O(nlogn) 空间复杂度O(n)
是稳定性排序，不是原地排序
"""
class MergeSort():
    def mergesort(self, list_a, list_b):
        """
        :param list_a: 有序数组a
        :param list_b: 有序数组b
        :return:
        """
        i = 0
        j = 0
        list_new = []
        while i+1<=len(list_a) and j+1 <= len(list_b):
            if list_a[i] >= list_b[j]:
                list_new.append(list_b[j])
                j = j+1
            else:
                list_new.append(list_a[i])
                i = i+1
        # 可优化点，这里判断了两次，可以使用哨兵进行优化
        if i+1 <= len(list_a):
            list_new.extend(list_a[i:])
        else:
            list_new.extend(list_b[j:])
        print(list_new)


a = [1,2,3,4,5,11]
b = [2,6,7,8,9,10]
MergeSort().mergesort(a, b)
